import java.util.Arrays;


public class MaxHeap implements Heap
{
	private Comparable[] arr;
	
	public MaxHeap(Comparable[] arr)
	{
		this.arr = arr;
		heapifyTopDown();
	}
	public void heapifyTopDown()
	{
		for(int end = 0; end < arr.length; end++)
		{
			siftUp(0, end);
		}
	}
	private void siftUp(int start, int cIndex)
	{
		while(cIndex > start)
		{
			Comparable child = arr[cIndex];
			Comparable parent = arr[((cIndex - 1) / 2)];
			int pIndex = (cIndex - 1) / 2;
			if (child.compareTo(parent) > 0)
			{
				swap(pIndex, cIndex);
				cIndex = pIndex;
			}
			else
				return;
		}
	}
	private void swap(int a, int b)
	{
		Comparable temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}
	public Comparable[] getArr()
	{return arr;}
	public String toString()
	{
		String str = "";
		for(Comparable c : arr)
		{
			str += c.toString() + " ";
		}
		return str;
	}
	
}
